package com.haidechizi.leetcode;

/**
 * @author: wangdejun
 * @create: 2020-04-23 11:05
 **/
public class _4_寻找两个有序数组的中位数 {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] tempArr = merge(nums1, nums2);
        int length = tempArr.length;
        if (length % 2 == 1) {
            return tempArr[tempArr.length / 2];
        }
        int middle = tempArr.length / 2;
        return ((double) (tempArr[middle - 1] + tempArr[middle])) / 2;
    }

    public int[] merge(int[] nums1, int[] nums2) {
        int[] tempArr = new int[nums1.length + nums2.length];
        int i = 0, j = 0;
        int index = 0;
        os:
        while (i < nums1.length && j < nums2.length) {
            while (i < nums1.length && nums1[i] <= nums2[j]) {
                tempArr[index] = nums1[i];
                i++;
                index++;
                if (i >= nums1.length) {
                    break os;
                }
            }
            while (j < nums2.length && nums1[i] > nums2[j]) {
                tempArr[index] = nums2[j];
                j++;
                index++;
                if (j >= nums2.length) {
                    break os;
                }
            }
        }
        while (i < nums1.length) {
            tempArr[index] = nums1[i];
            i++;
            index++;
        }

        while (j < nums2.length) {
            tempArr[index] = nums2[j];
            j++;
            index++;
        }
        return tempArr;
    }


    public static void main(String[] args) {
        new _4_寻找两个有序数组的中位数().
                findMedianSortedArrays(new int[]{1, 2}, new int[]{3, 4});
    }
}
